package com.yoshino.leetcode.oneHundred.twentytwoth;

import java.util.Arrays;

class Solution {
    public int[] singleNumbers(int[] nums) {
        // 同一个数取 异或 得0
        // 不同数取异或 肯定会有一个 xx1xx 留下
        int res = 0;
        for (int num : nums) {
            res ^= num;
        }
        // 获取其中一个 1 （取最低位的）
        int m = 1;
        while ((m & res) == 0) {
            m <<= 1;
        }
        int x = 0, y = 0;
        // 该不同数对于 m 取 & 一定有两种结果，将其分开计算
        // 同一个数则会有相同结果
        for (int num : nums) {
            if ((num & m) == 0) {
                x ^= num;
            } else {
                y ^= num;
            }
        }
        return new int[]{x, y};
    }

    public int singleNumber(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 3; i+=3) {
            if (nums[i] != nums[i + 2]) {
                return nums[i];
            }
        }
        return nums[nums.length - 1];
    }
}